package com.sicheng.lc.杂题.二叉树;

import leetcode.editor.cn.tree.TreeNode;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/25 15:13
 */
public class 二叉搜索树 {
    TreeNode root;

    TreeNode build(int[] data) {
        if (data == null || data.length == 0)
            return null;
        root = new TreeNode(data[0]);
        for (int i = 1; i < data.length; i++) {
            build(root, data[i]);
        }
        return root;
    }

    private TreeNode build(TreeNode root, int v) {
        if (root == null) {
            return new TreeNode(v);
        }
        if (v >= root.val)
            root.right = build(root.right, v);
        else
            root.left = build(root.left, v);
        return root;
    }

    private TreeNode search(TreeNode root, int v) {
        if (root == null || root.val == v)
            return root;
        if (v > root.val)
            return search(root.right, v);
        return search(root.left, v);
    }

    private TreeNode delete(TreeNode root, int key) {
        //如果根节点为空，直接返回
        if (root == null) {
            return null;
        }
        //找到要删除的节点了
        if (root.val == key) {
            //如果要删除的节点为叶子节点，则直接删除
            if (root.left == null && root.right == null) {
                return null;
            }
            //要删除节点的左子树为空，右子树不为空，则返回右孩子节点
            else if (root.left == null) {
                return root.right;
            }
            //要删除节点的右子树为空，左子树不为空，则返回左孩子节点
            else if (root.right == null) {
                return root.left;
            }
            //左右子树都不为空，将左子树移动到右子树最左边节点的左孩子位置,返回右孩子节点
            else {
                TreeNode cur = root.right;
                while (cur.left != null) {
                    cur = cur.left;
                }
                cur.left = root.left;
                return root.right;
            }
        }
        //要删除的节点在左子树
        if (root.val > key) {
            root.left = delete(root.left, key);
        }
        //要删除的节点在右子树
        if (root.val < key) {
            root.right = delete(root.right, key);
        }
        return root;
    }

    public static void main(String[] args) {
        二叉搜索树 tree = new 二叉搜索树();
        int[] data = {4, 1, 2, 0, 5, 3};
        System.out.println(tree.build(data));
    }
}
